常見程式演算 :: 背包問題

您所在的位置：网站首页 › knap sack › 常見程式演算 :: 背包問題

常見程式演算 :: 背包問題

2023-03-24 18:14| 来源: 网络整理| 查看: 265

背包問題 December 1, 2021

假設背包負重最多可達 8 公斤，希望在背包中裝入的物品，在負重範圍內可得最高總價，假設是水果好了，水果的編號、單價與重量如下所示：

編號種類重量價格 0 李子 4KG 4500 1 蘋果 5KG 5700 2 橘子 2KG 2250 3 草莓 1KG 1100 4 甜瓜 6KG 6700 解法思路

背包問題是關於最佳化的問題，可以使用動態規劃（Dynamic programming），試著解決構成的大問題之小問題，基於小問題的最佳解答來解決大問題，最後得到的就是大問題的最佳解。

以背包問題為例，要解決背包負重為 8 公斤，水果有 5 個的問題，可以先解決背包負重為 1 公斤，水果有 1 個的問題，接著解決背包負重為 2 公斤，水果有 1 個的問題，然後解決背包負重為 3 公斤，水果有 1 個的問題…

一種水果

若使用兩個陣列 value 與 item，value 表示目前負重下可得的最大總價，一開始都是 0，item 表示最後放至背包的水果，首先是只有李子，從可以負重 1 公斤到可以負重 8 公斤，能得到的最大總價各是：

背包負重 value item 1 0 - 2 0 - 3 0 - 4 4500 0 5 4500 0 6 4500 0 7 4500 0 8 9000 0

只有李子的情況下，可以直覺地建立以上表格，不過現在觀察出演算方式，首先在負重 3 公斤以下時，不可能放入李子，總價皆為 0，4 公斤時可放入一個李子，價值為 4500 元，還可以負擔 0 公斤，對應的價值為 0 元，4500 + 0 的總價大於目前對應的 value 值，於是更新 value 與 item。

類似地，5 公斤時可以放入一個李子，價值為 4500 元，還可以負擔 1 公斤，對應的價值為 0 元，4500 + 0 的總價大於目前對應的 value 值，於是更新…

8 公斤時可以放入一個李子，價值為 4500 元，還可以負擔 4 公斤，對應的價值為 4500 元，4500 + 4500 的總價大於目前對應的 value 值，於是更新…

因此在可以負重 8 公斤，只有李子的情況下，可以得到的最大總價是 9000 元，最後放入的李子是 4 公斤，裝入這顆李子前，背包能負重的是 4 公斤的水果，4 公斤處對應的水果是李子，因此目前最佳解為9000元，兩顆李子。

兩種水果

接著處理背包負重為 1 公斤，水果有 2 個的問題；背包負重為 2 公斤，水果有 2 個的問題；背包負重為3公斤，水果有 2 個的問題…因為方才已經處理過只有李子的運算，現在可以基於其結果，直接考慮該如何置入蘋果。

負重 4 公斤以下的情況，不可能放入蘋果，對應的 value、item 都不用更新，負重 5 公斤時，若先放入蘋果，表示只剩下 1 公斤負重，目前對應的 value 為 0 元，5700 + 0 大於目前 5 公斤對應的 value 值 4500，於是予以更新 value 與 item，負重 6、7 公斤時也都是這麼運算，負重 8 公斤時，若先放入蘋果，表示只剩下 3 公斤負重，對應的 value 為 0 元，0 + 5700 不大於目前的 value 值 9000，於是不更新。

背包負重 value item 1 0 - 2 0 - 3 0 - 4 4500 0 5 5700 1 6 5700 1 7 5700 1 8 9000 0

因此在可以負重 8 公斤，只有李子、蘋果的情況下，可以得到的最大總價是 9000 元，最後放入的李子是 4 公斤，裝入這顆李子前，背包能負重的是 4 公斤的水果，4 公斤處對應的水果是李子，因此目前最佳解為 9000 元，兩顆李子。

更多種水果

接著處理背包負重為 1 公斤，可能的水果有 3 個的問題，背包負重為 2 公斤，可能的水果有 3 個的問題，背包負重為3公斤，可能的水果有 3 個的問題…因為方才已經處理過只有李子、蘋果的運算，現在可以基於其結果，直接考慮該如何置入橘子，依方才的演算方式，可以得到：

背包負重 value item 1 0 - 2 2250 2 3 2250 2 4 4500 0 5 5700 1 6 6750 2 7 7950 2 8 9000 0

接著基於以上，處理加上草莓的情況：

背包負重 value item 1 1100 3 2 2250 2 3 3350 3 4 4500 0 5 5700 1 6 6800 3 7 7950 2 8 9050 3

接著基於以上，處理加上甜瓜的情況：

背包負重 value item 1 1100 3 2 2250 2 3 3350 3 4 4500 0 5 5700 1 6 6800 3 7 7950 2 8 9050 3

由最後一個表格，可以得知在背包負重 8 公斤時，最多可以裝入 9050 元的水果，而最後一個裝入的水果是 3 號，也就是草莓，裝入了草莓，背包只能再放入 7 公斤的水果，所以必須看背包負重7公斤時的最佳解，最後一個放入的是 2 號，也就是橘子，現在背包剩下負重量 5 公斤，所以看負重 5 公斤的最佳解，最後放入的是 1 號，也就是蘋果，此時背包負重量剩下 0 公斤，無法再放入水果，所以求出最佳解為放入草莓、橘子與蘋果，而總價為 9050 元。

程式實作 #include #include #define LIMIT 8 // 重量限制 typedef struct { char name[20]; int weight; int price; } Fruit; void knapsack(Fruit*, int*, int*, int, int); int min(Fruit*, int); int main(void) { Fruit fruits[] = {{"李子", 4, 4500}, {"蘋果", 5, 5700}, {"橘子", 2, 2250}, {"草莓", 1, 1100}, {"甜瓜", 6, 6700}}; int items[LIMIT + 1] = {0}; int values[LIMIT + 1] = {0}; int length = sizeof(fruits) / sizeof(fruits[0]); knapsack(fruits, values, items, length, LIMIT); printf("物品\t價格\n"); int i; for(i = LIMIT; i >= min(fruits, length); i -= fruits[items[i]].weight) { printf("%s\t%d\n", fruits[items[i]].name, fruits[items[i]].price); } printf("合計\t%d\n", values[LIMIT]); return 0; } void knapsack(Fruit* fruits, int* values, int* items, int length, int limit) { int i, w; for(i = 0; i = minWeight else []) return solution(limit, iterate(len(fruits) - 1)[1], min([f[1] for f in fruits])) print(knapsack([('李子', 4, 4500), ('蘋果', 5, 5700), ('橘子', 2, 2250), ('草莓', 1, 1100), ('甜瓜', 6, 6700)], 8)) case class Fruit(name: String, weight: Int, price: Int) def knapsack(fruits: List[Fruit], limit: Int) = { def nextVI(i: Int, values: List[Int], items: List[Int]) = { val viList = (for(w = fruits(i).weight && w values(w)) (values(w - fruits(i).weight) + fruits(i).price, i) else (values(w), items(w))) ((Nil : List[Int], Nil : List[Int]) /: viList) { (vis: (List[Int], List[Int]), vi: (Int, Int)) => (vis._1 ++ List(vi._1), vis._2 ++ List(vi._2)) } } def iterate(i: Int): (List[Int], List[Int]) = { if(i == 0) { val arr = new Array[Int](limit + 1) nextVI(i, arr.toList, arr.toList) } else { val (values, items) = iterate(i - 1) nextVI(i, values, items) } } case class Fruit(name: String, weight: Int, price: Int) def knapsack(fruits: List[Fruit], limit: Int) = { def nextVI(i: Int, values: List[Int], items: List[Int]) = { val viList = (for(w = fruits(i).weight && w values(w)) (values(w - fruits(i).weight) + fruits(i).price, i) else (values(w), items(w))) (viList :\ (Nil : List[Int], Nil : List[Int])) { (vi: (Int, Int), vis: (List[Int], List[Int])) => (vi._1 :: vis._1, vi._2 :: vis._2) } } def iterate(i: Int): (List[Int], List[Int]) = { if(i == 0) { val arr = new Array[Int](limit + 1) nextVI(i, arr.toList, arr.toList) } else { val (values, items) = iterate(i - 1) nextVI(i, values, items) } } def solution(i: Int, items: List[Int], minWeight: Int): List[Fruit] = { if(i >= minWeight) fruits(items(i)) :: solution( i - fruits(items(i)).weight, items, minWeight) else Nil } solution(limit, iterate(fruits.size - 1)._2, fruits.map(fruit => fruit.weight).min) } println(knapsack(List(Fruit("李子", 4, 4500), Fruit("蘋果", 5, 5700), Fruit("橘子", 2, 2250), Fruit("草莓", 1, 1100), Fruit("甜瓜", 6, 6700)), 8)) # encoding: UTF-8 def knapsack(fruits, limit) nextVI = ->(i, values, items) { (0...values.size).map { |w| if w >= fruits[i][:weight] and w values[w] {value: values[w - fruits[i][:weight]] + fruits[i][:price], item: i} else {value: values[w], item: items[w]} end }.reduce({values: [], items: []}) { |vis, vi| {values: vis[:values] + [vi[:value]], items: vis[:items] + [vi[:item]]} } } iterate = ->(i) { if i == 0 nextVI.call(i, [0] * (limit + 1), [0] * (limit + 1)) else vis = iterate.call(i - 1) nextVI.call(i, vis[:values], vis[:items]) end } solution = ->(i, items, minWeight) { if i >= minWeight [fruits[items[i]]] + solution.call(i - fruits[items[i]][:weight], items, minWeight) else [] end } solution.call(limit, iterate.call(fruits.size - 1)[:items], fruits.map { |fruit| fruit[:weight] }.min) end def fruit(n, w, p) {name: n, weight: w, price: p} end knapsack([fruit('李子', 4, 4500), fruit('蘋果', 5, 5700), fruit('橘子', 2, 2250), fruit('草莓', 1, 1100), fruit('甜瓜', 6, 6700)], 8).each do |fruit| print "(#{fruit[:name]}, #{fruit[:weight]}, #{fruit[:price]})" end function fruit(n, w, p) { return { name : n, weight : w, price : p }; } function knapsack(fruits, limit) { Array.prototype.reduce = function(init, f) { var value = init; for(var i = 0; i = minWeight) { return [fruits[items[i]]].concat( solution(i - fruits[items[i]].weight, items, minWeight)); } else { return []; } } return solution(limit, iterate(fruits.length - 1).items, fruits.reduce(fruits[0].weight, function(seed, elem) { return elem weight f) fruits) where nextVI i values items = let viList = [if w >= weight (fruits !! i) && w values !! w then (values !! (w - weight (fruits !! i)) + price (fruits !! i), i) else (values !! w, items !! w) | w (fst vi : fst vis, snd vi : snd vis)) ([], []) viList iterate i = if i == 0 then nextVI i [0 | i iterate(fruits.get(i).weight, limit + 1).forEach(w -> trySolution(i, w, fruits, values, limit) ) )) } def trySolution(i, w, fruits, values, limit) { p = w - fruits.get(i).weight newValue = values.get(p) + fruits.get(i).price if newValue > values.get(w) { values.set(w, newValue) items.set(w, i) } } (fruits = [ new Fruit('李子', 4, 4500), new Fruit('蘋果', 5, 5700), new Fruit('橘子', 2, 2250), new Fruit('草莓', 1, 1100), new Fruit('甜瓜', 6, 6700) ]) WEIGHT_LIMIT = 8 items = List.create(WEIGHT_LIMIT, 0) values = List.create(WEIGHT_LIMIT, 0) def fruit(i) { return fruits.get(items.get(i)) } knapsack(fruits, values, items, WEIGHT_LIMIT) min_weight = min(fruits.map(fruit -> fruit.weight)) (iterate(WEIGHT_LIMIT, i -> i >= min_weight, i -> i - fruit(i).weight) .forEach(i -> println(fruit(i)))) println('${0}'.format(values.get(WEIGHT_LIMIT)))

【本文地址】

常見程式演算 :: 背包問題

常見程式演算 :: 背包問題

今日新闻

推荐新闻